import java.text.DecimalFormat;
import java.util.Arrays;

public class homework2 {


    public static void main(String[] args) {
        int[] weights = {500, 200, 100, 400, 300};
        int[] persons = {5, 3, 2, 3, 3};

        int result = mine(weights, persons, 10);
        System.out.println(result);
    }

    static int mine(int[] weights, int[] persons, int personNum) {

        // int[人數][金礦重]
        int[][] dp = new int[personNum + 1][weights.length + 1];

        // 人數遍歷
        for (int i = 1; i <= personNum; i++) {

            // 金礦遍歷
            for (int j = 1; j < weights.length + 1; j++) {

                if (i < persons[j-1]) {
                    dp[i][j] = dp[i][j-1];
                } else {
                    if (i-persons[j-1] >= 0) {
                        dp[i][j] = Math.max(dp[i][j-1], weights[j-1] + dp[i-persons[j-1]][j-1]);
                    } else {
                        dp[i][j] = Math.max(dp[i][j-1], 0);
                    }

                }
            }
        }


        for (int j = 1; j < dp[j].length; j++) {
            for (int i = 1; i < dp.length; i++) {
                System.out.print(new DecimalFormat("0000").format(dp[i][j]) + ",");
            }
            System.out.println();
        }

        return dp[personNum][weights.length];
    }
}
